1. Field of the Invention
The invention relates to image processing methods for reducing noise in a sampled image. More specifically, the invention pertains to such methods in which an image is divided into blocks of sampled image elements which are transformed according to a linear transform procedure.
2. Description Relative to the Prior Art
Known image processing apparatus commonly uses two kinds of methods for reducing noise in a sampled representation of an image: (1) one kind of method based on a point-neighborhood process and (2) another kind of method based on a transform process. In both kinds of methods, every sampled image value is replaced by a modified value, based on the image values within a surrounding field of image elements. The values within the surrounding field are used to form a number of different linear combinations each of which represents a different component of the image structure within the field, and most of which represent the detail within the field. Each detail-sensitive combination represents a difference among local image values and tends to vanish in the absence of a particular kind of image detail. Noise is reduced by modifying the detail-sensitive combinations such that, for example, the value of a combination is lowered or set to zero whenever a particular kind of image detail is not present to a significant degree.
Point-neighborhood processes consider the value of each original element separately in combination with the values in a small neighborhood of surrounding elements. These processes reconsitute the image by replacing the value of each original image element by the sum of a number of linear combinations of the neighborhood values.
Transform processes may use instead of a small neighborhood the whole array of sampled image values, as described by Agrawal and Jain, (in "Bandwidth Compression of Noisy Images," Computer and Electronic Engineering, Vol. 2, 1975, pp. 275-284) and Keshavan et al (in "Application of Orthogonal Transforms in the Enhancement of Images in the Presence of Additive Noise," Computer and Electronic Engineering, Vol. 4, 1977, pp. 279-295). In a transform process, the original image is represented by a combination of predetermined patterns (i.e., functions). Each pattern is numerically weighted by a transform coefficient calculated from a linear combination of the image values. The magnitude of each transform coefficient indicates the contribution of the corresponding pattern to the original image. The transform coefficients of all of these patterns thus constitute the original image in its transformed condition. The image (in its original condition) may be recovered by replacing the image value of each element by a different linear combination of the transform coefficients.
In both point-neighborhood and transform processes noise is reduced by modifying the detail-sensitive linear combinations of the image values. Since the noise modification process involves the application of a non-linear function, some distortion of local image values (i.e., an artifact of the processing itself) may be generated which affects the wanted image and the residue of unwanted noise, but this is tolerated in order to realize the desired noise reduction.
For a typical image, a transform process carries out direct and inverse transform computations on a large array of data. In the case of data compression by a transform process, Wintz (in "Transform Picture Coding," Proceedings of the IEEE, Vol. 60, No. 7, July 1972, pp. 809-820) describes dividing the image into adjacent blocks of image elements in order to simplify coding for image transmission. Division of the image into blocks faacilitates processing not only for image coding, but also for noise reduction. Processing each block independently for noise reduction reduces the computation load and the problem of managing large arrays of data. The total number of transform coefficients to be generated for later modification is reduced only slightly, but each one involves less computation.
Unfortunately, there is also a disadvantage associated with dividing the image into blocks. After modification and inverse transformation, a boundary may exist between adjacent blocks. These boundaries may lead to a checkerboard appearance in the reconstituted image, acceptable in some applications, but unacceptable for high quality image reproduction. Nicholson and Davis (in "The Binomial Window", SPIE Vol. 238, Image Processing for Missile Guidance, pp. 467-479) say that this defect can be reduced by multiple runs of the block process over the image, incrementing the block address between runs so as to provide block/block overlap. They point out, however, that computational cost (or time) usually limits block processing practice to adjacent, non-overlapping image blocks.
The selection of the block size in a block transform process intended for noise reduction must be considered carefully. If the block size is too small, noise components of low spatial frequency will remain unchaanged after modification of the coefficients and may result in a residual mottled appearance. In some applications involving images of moderate quality and spatial resolution, a small block, containing relatively few elements, provides an adequate degree of noise reduction. Such an application is described by Ebihara (U.S. Pat. No. 4,163,258). In these cases, the technique of multiple runs with block overlap, as proposed by Nicholson and Davis, will solve the block boundary problem without requiring excessive computation. In other applications involving images of higher quality, however, a large block, containing a relatively large number of elements, is needed to suppress mottle. Using such a block not only increases the computation load, especially if overlap is used, but also degrades high-frequency detail that is confined to a small area within the block.
For these reasons, it is better for purposes of noise reduction to process the image with several block sizes and to use overlap to avoid the appearance of checkerboard patterns. Depending on the method adopted, demands on computational time and capacity may be excessive. In the case of an image coding system, Lux (U.S. Pat. No. 4,134,134) has proposed reducing the computational load by processing in a series of stages, as follows. In the first stage, the image is divided into blocks, and each of these blocks is transformed. One coefficient of each transformed block represents the average within that block. At the second stage, these average coefficients are employed to form a reduced image derived from the block averages in the previous stage. That reduced image is divided into blocks, each is transformed, and the coefficients representing averages are used to form a still further reduced image. Since the number of blocks in the first stage is less than the number of elements in the first stage, the second stage requires considerably less computation than the first. Subsequent stages can be implemented with less and less additional computation.
For the purpose of noise reduction, which was not considered by Lux, such a multi-stage procedure has the advantage of processing with several block sizes. Small blocks, containing only a few local picture elements, are used for processing high-spatial frequencies, while large blocks, containing averages from the small blocks and representative of many picture elements, are used for processing low-spatial frequencies. Local areas of high-frequency image detail are now represented by only a few coefficients generated in relation to the small blocks which contain that detail. This allows more of the high-frequency noise in other areas to be removed without degrading high frequency image detail in those blocks in which it occurs. Furthermore, while Lux does not suggest overlap, operating in stages reduces the computational load so that overlapping of blocks becomes practical. This overlap reduces the visibility of block boundaries.
The method in accordance with the invention utilizes the combination of a block overlap transform process and a multi-stage procedure to overcome the problem of boundary visibility in an image processing method intended for noise reduction. Besides reducing the amount of processing to a manageable level while still using several block sizes, this combined solution to the problem of block visibility has another advantage. In order to understand this advantage, consider first the case of a multi-stage procedure with non-overlapping boundaries. Each image element falls into one block of each size. The value of each image element after processing is the linear combination of (1) the modified detail-sensitive transform coefficients from one block of every stage, and (2) the average value from one block of the largest size of the series. In contrast, in the case of a multi-stage procedure with overlap, the value of each element after processing and averaging over the multiple runs depending on a much larger number of coefficients. These coefficients are (1) the modified detail-sensitive transform coefficients from every block that overlaps that element at every stage and (2) the average values from all of the largest blocks that overlap that element. The actual number of contributions depends on the number of stages, the size of the transform block at each stage and the amount of overlap employed at each stage. The values of corresponding coefficients from all of the blocks overlapping each element will be different, and each will be modified differently by the non-linear noise reduction process. As explained earlier, the local distortion (i.e., artifact) associated with this non-linear modification affects the wanted image component and the residue of unwanted noise component. However, averaging over a large number of overlapped partial images, as prescribed by the invention in order to reduce block visibility, also reduces the visibility of the artifacts in both components of the image, thus improving the effective noise reduction performance.